package jzoffer;

/**
 * 使用快速幂
 * x^n 实际就是 对x^n化简 n每次/2，x每次平方，期间如果n是奇数 则需要提出一个x，x^n就是所有n为奇数为提出来的x的乘积
 * @<code>
 *      long res=1;
 *       3^10
 *     = (3^2)^5=9^5 * res             (res=1 不变)
 *     = (9^2)^(5/2) * 9=81^2  * 9    (res=9*1 )
 *     = (81*81)^1 * 9                (res=9*1 不变)
 *     = 幂为1又是奇数 1/2=0 结果为1
 *     = (81^4)^0 * (9*81*81)        (res=9*1*81^2 )
 *     最终3^10=res
 * </code>
 * @author MaoLin Wang
 * @date 2020/10/7 9:26 上午
 */
public class xN次幂 {

    public static double  xn(double x,int n){
        if (x==0){
            return 0;
        }
        long b=n;
        if (b<0){
            x=1/x;
            b=-b;
        }
        double res=1.0;
        while (b>0){
            if ((b&1)==1){
                res*=x;
            }
            x*=x;
            b>>=1;
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(xn(2,5));
    }
}
